package com.yusong.algorithm;


import com.yusong.algorithm.data.DataConstants;

/**
 * 插入排序
 * 对选择排序不利用已排序队列的改善，所需要的比较次数只有选择排序的一半
 */
public class InsertSort extends AbstractSort {

    @Override
    public void sort(Comparable[] a) {
        int length = a.length;
        for (int i = 0; i < length-1; i++) {
            for (int j = i + 1; j >= 1; j--) {
                if(!less(a[j],a[j-1])){
                    break;
                }
                exchange(a,j,j-1);
            }
        }
    }

    public static void main(String[] args) {
        InsertSort insertSort = new InsertSort();
        insertSort.sort(DataConstants.NUM_SIMPLE);
        show(DataConstants.NUM_SIMPLE);
    }
}

/**
 * 插入排序说明
 * 算法：类似于清理扑克牌
 * 适合部分有序的序列，插入排序对这样的数组很有效，而选择排序则不然。
 * 事实上，当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。
 * 优化：内循环中，只需要将较大的数据向右移动，而不是每次交换
 */
